import argparse
v = False #verbose (default: no)

#Basic pair of function based on the inductive proof.
#Too many functions, it must be shortened.

def binary_tuple(n, lvl=0):
	"""
	Computes the number of binary sequences ending with 0 and 1.
	The result is stored in a tuple to compute it recursively.
	>>> print binary_tuple(1)
	(1, 1)
	>>> print binary_tuple(2)
	(1, 2)
	>>> print binary_tuple(3)
	(2, 3)
	"""
	if n == 1:
		r = (1, 1)
		if v: print " "*lvl+"binary_tuple", n, "r", r
	else:
		(x, y) = binary_tuple(n-1, lvl+1)
		r = (y, x+y)
		if v: print " "*lvl+"binary_tuple", n, [x, y], "r", r
	return r

def binary(n):
	"""
	Computes the total number of binary sequences of the given length.
	>>> print binary(0)
	1
	>>> print binary(1)
	2
	>>> print binary(2)
	3
	>>> print binary(3)
	5
	"""
	if n == 0: 
		return 1 #empty
	else:
		return sum(binary_tuple(n))

#Iterative version of binary_tuple, simply added the n=0 case and computed the sum.

def binary_it(n):
	"""
	Computes the total number of binary sequences of the given length.
	>>> print binary_it(0)
	1
	>>> print binary_it(1)
	2
	>>> print binary_it(2)
	3
	>>> print binary_it(3)
	5
	"""
	if n == 0:
		return 1 #empty
	else:
		(x, y) = (1, 1)
		while n != 1:
			(x, y) = (y, x+y)
			n -= 1
		return x+y

#Recursive version of binary_it, added parameters with a default value.

def binary_rec(n, x=1, y=1, lvl=0):
	"""
	Computes the total number of binary sequences of the given length.
	>>> print binary_rec(0)
	1
	>>> print binary_rec(1)
	2
	>>> print binary_rec(2)
	3
	>>> print binary_rec(3)
	5
	"""
	if n == 0:
		r = 1 #empty
	elif n == 1:
		r = x+y
	else:
		r = binary_rec(n-1, y, x+y, lvl+1)
	if v: print " "*lvl+"binary_rec", n, [x, y], "r", r
	return r


parser = argparse.ArgumentParser()
parser.add_argument("length", type=int)
parser.add_argument("--debug", "-d", action="store_true")
parser.add_argument("--test", "-t", action="store_true")
args = parser.parse_args()
if args.test:
	import doctest
	doctest.testmod()
v = args.debug

binary_tuple(args.length)
binary_rec(args.length)
